//#pragma once
//#include<iostream>
//void Print(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		std::cout << arr[i] << " ";
//	}
//	std::cout << std::endl;
//}
//void Swap(int& x, int& y)
//{
//	int tmp = x;
//	x = y;
//	y = tmp;
//}
//void ShellSort(int* arr,int n)
//{
//	int gap = n;
//	while (gap>1)
//	{
//		gap = gap / 3 + 1;
//		for (int i=0;i<n-gap;i++)
//		{
//			int end = i;
//			int back_value = arr[end+gap];
//			while (end>=0)
//			{
//				if (arr[end]>back_value)
//				{
//					arr[end + gap] = arr[end];
//					end = end - gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			arr[end + gap] = back_value;
//		}
//	}
//}
//int main()
//{
//	int arr[] = { 5,9,1,6,2,3,4,8,7,10,15,11,16,12,14,13 };
//	int size = sizeof(arr) / sizeof(int);
//	ShellSort(arr, size);
//	Print(arr, size);
//	return 0;
//}